package com.leetcode.hashtable;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 * @author: ZhouBert
 * @date: 2019/9/28
 * @description: 409. 最长回文串
 * A
 * 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
 * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
 * <p>
 * 注意:
 * 假设字符串的长度不会超过 1010。
 * <p>
 * 示例 1:
 * 输入:
 * "abccccdd"
 * 输出:
 * 7
 * <p>
 * 解释:
 * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindrome
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LongestPalindrome409 {

	/**
	 * todo:11 ms	35.6 MB
	 * 思路基本一致
	 * @param s
	 * @return
	 */
	public static int longestPalindrome(String s) {
		if (s == null) {
			return 0;
		}

		///1.考虑使用数组，但是可能会浪费空间；于是考虑使用 map,记录不同 Char 的次数
		Map<Character, Integer> map = new LinkedHashMap<>();
		char[] chars = s.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			if (map.containsKey(chars[i])) {
				map.put(chars[i], map.get(chars[i])+1);
			} else {
				map.put(chars[i], 1);
			}
		}

		///是否存在奇数
		boolean haveOdd=false;
		int result=0;
		///2.
		for (Entry<Character, Integer> item :
				map.entrySet()) {
			if (item.getValue()%2==0){
				result+=item.getValue();
			}else {
				///当奇数时，需要获取-1后的值
				result+=item.getValue()-1;
				haveOdd=true;
			}
		}
		if (haveOdd){
			result++;
		}
		return result;
	}

	/**
	 * todo:1 ms	36.1 MB	没想到时间最少，可能是创建数组最省时间了
	 * A → 65	z → 122
	 * @param s
	 * @return
	 */
	public static int longestPalindrome2(String s){
		if (s == null) {
			return 0;
		}
		int[] store=new int[58];
		char[] chars = s.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			int temp = chars[i] - 'A';
			store[temp]++;
		}

		boolean haveOdd=false;
		int result=0;
		for (int i = 0; i < 52; i++) {
			if (store[i]%2==0){
				result+=store[i];
			}else{
				result+=store[i]-1;
				haveOdd=true;
			}
		}
		if(haveOdd){
			result++;
		}
		return result;
	}

	public static void main(String[] args) {
		String str = "abccccdd";
		str="AAAAAA";
		int len = longestPalindrome(str);
		int len2 = longestPalindrome2(str);
		System.out.println(len);
		System.out.println(len2);
	}
}
